package com.arron.algorithm.leetcodetop100.单调栈;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.stream.Stream;

public class 移掉K位数字 {

    //使用双向链表代替 stack 效率会更好
    LinkedList<Character> stack = new LinkedList<>();

    public String removeKdigits(String num, int k) {
//
//        int[] nums = Stream.of(num.toCharArray()).mapToInt(i->Integer.parseInt(Arrays.toString(i))).toArray();
//
        if (num.length() == k){
            return "0";
        }
        char[] chars = num.toCharArray();


        for (char aChar : chars) {
            while (!stack.isEmpty() && stack.getLast() > aChar){
                if (k ==0){
                    break;
                }
                stack.pollLast();
                k--;
            }
            stack.offerLast(aChar);

        }
        // k!=0 ，则说明还存在没有移除完的数字，还需要继续移除 按照以上贪心策略直接移除末尾的数字即可，因为前面的数字都比自己大
        while ( k!=0 ){
            stack.pollLast();
            k--;
        }


        // 拼接字符串并反转
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()){

            sb.append(stack.pollLast());
        }
        String s = sb.reverse().toString();
        // 去除前导 0
        while (s.length() >1 && s.startsWith("0")){
            s = s.substring(1, s.length());
        }

        return s;
    }

    public static void main(String[] args) {

        移掉K位数字 removek = new 移掉K位数字();

        String  num = "10001";

        System.out.println(removek.removeKdigits(num, 2));


    }

}
